#include<iostream>
#include<vector>
#include<unordered_map>
#include<queue>
using namespace std;

class Solution {
    int m, n;
    int dx[4] = { 1,-1,0,0 };
    int dy[4] = { 0,0,-1,1 };
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        m = mat.size(), n = mat[0].size();
        vector<vector<int>> dict;
        dict.resize(m);
        for (int i = 0; i < m; i++)
            dict[i].resize(n, -1);

        queue<pair<int, int>> qu;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (mat[i][j] == 0) {
                    qu.push(make_pair(i, j));
                    dict[i][j] = 0;
                }

        while (!qu.empty()) {
            pair<int, int> tmpPos = qu.front();
            qu.pop();
            for (int i = 0; i < 4; i++) {
                int xx = tmpPos.first + dx[i];
                int yy = tmpPos.second + dy[i];
                if (xx >= 0 && xx < m && yy >= 0 && yy < n && mat[xx][yy] == 1 && dict[xx][yy] == -1) {
                    dict[xx][yy] = dict[tmpPos.first][tmpPos.second] + 1;
                    qu.push(make_pair(xx, yy));
                }
            }
        }
        return dict;
    }
};

//class Solution {
//    int m, n;
//    int dx[4] = { 1,-1,0,0 };
//    int dy[4] = { 0,0,-1,1 };
//public:
//    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
//        m = mat.size(), n = mat[0].size();
//        vector<vector<int>> dict(m, vector<int>(n, -1));
//
//        queue<pair<int, int>> qu;
//        for (int i = 0; i < m; i++)
//            for (int j = 0; j < n; j++)
//                if (mat[i][j] == 0) {
//                    qu.push(make_pair(i, j));
//                    dict[i][j] = 0;
//                }
//
//        while (!qu.empty()) {
//            // auto [a, b] = qu.front();
//            qu.pop();
//            for (int i = 0; i < 4; i++) {
//                int xx = a + dx[i];
//                int yy = b + dy[i];
//                if (xx >= 0 && xx < m && yy >= 0 && yy < n && mat[xx][yy] == 1 && dict[xx][yy] == -1) {
//                    dict[xx][yy] = dict[a][b] + 1;
//                    qu.push(make_pair(xx, yy));
//                }
//            }
//        }
//        return dict;
//    }
//};

class Solution {
    int dx[4] = { 0,0,-1,1 };
    int dy[4] = { 1,-1,0,0 };
public:
    int numEnclaves(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        queue<pair<int, int>> qu;
        for (int i = 0; i < m; i++) {
            if (grid[i][0] == 1) {
                qu.push(make_pair(i, 0));
                grid[i][0] = 0;
            }
            if (grid[i][n - 1] == 1) {
                qu.push(make_pair(i, n - 1));
                grid[i][n - 1] = 0;
            }
        }
        for (int j = 1; j < n - 1; j++) {
            if (grid[0][j] == 1) {
                qu.push(make_pair(0, j));
                grid[0][j] = 0;
            }
            if (grid[m - 1][j] == 1) {
                qu.push(make_pair(m - 1, j));
                grid[m - 1][j] = 0;
            }
        }
        while (!qu.empty()) {
            pair<int, int> tmpPos = qu.front();
            qu.pop();
            for (int i = 0; i < 4; i++) {
                int xx = tmpPos.first + dx[i];
                int yy = tmpPos.second + dy[i];
                if (xx >= 0 && xx < m && yy >= 0 && yy < n && grid[xx][yy] == 1) {
                    grid[xx][yy] = 0;
                    qu.push(make_pair(xx, yy));
                }
            }
        }
        long long ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) ans++;
            }
        }
        return ans;
    }
};

class Solution {
    int dx[4] = { 1,-1,0,0 };
    int dy[4] = { 0,0,-1,1 };
public:
    vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {
        int m = isWater.size(), n = isWater[0].size();
        vector<vector<int>> ans;
        ans.resize(m, vector<int>(n, -1));
        queue<pair<int, int>> qu;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (isWater[i][j] == 1) {
                    ans[i][j] = 0;
                    qu.push(make_pair(i, j));
                }
            }
        }
        while (!qu.empty()) {
            pair<int, int> tmpPos = qu.front();
            qu.pop();
            for (int i = 0; i < 4; i++) {
                int xx = tmpPos.first + dx[i];
                int yy = tmpPos.second + dy[i];
                if (xx >= 0 && xx < m && yy >= 0 && yy < n && ans[xx][yy] == -1) {
                    ans[xx][yy] = ans[tmpPos.first][tmpPos.second] + 1;
                    qu.push(make_pair(xx, yy));
                }
            }
        }
        return ans;
    }
};

class Solution {
    int dx[4] = { 0,0,-1,1 };
    int dy[4] = { 1,-1,0,0 };
public:
    int maxDistance(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        queue<pair<int, int>> qu;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    qu.push(make_pair(i, j));
                }
            }
        }
        if (qu.empty() || qu.size() == m * n) return -1;
        int ret = 0;
        while (!qu.empty()) {
            ret++;
            int leveld = qu.size();
            while (leveld--) {
                pair<int, int> tmpPos = qu.front();
                qu.pop();
                for (int i = 0; i < 4; i++) {
                    int xx = tmpPos.first + dx[i];
                    int yy = tmpPos.second + dy[i];
                    if (xx >= 0 && xx < m && yy >= 0 && yy < n && grid[xx][yy] == 0) {
                        grid[xx][yy] = 1;
                        qu.push(make_pair(xx, yy));
                    }
                }
            }
        }
        return ret - 1;
    }
};